//
// Created by admin on 24-12-16.
//

#ifndef SEGTREEFORSCANLINE_H
#define SEGTREEFORSCANLINE_H
#include <iostream>
#include <vector>
using namespace std;
//在这里面统一将l r表示线段树负责的idx的l和r,而L R代表的是实际负责的线段离散的后的线段
struct Segment {
    int l,r; //l,r代表负责的范围
    long long sum = 0;
    long long len = 0;
    //  sum: 被完全覆盖的次数；
    //  len: 区间内被截的长度

    //重载+
    Segment operator + (const Segment &rhs) const {
        return Segment(len + rhs.len);
    }

};
class SegTreeForScanLine {
    private:
    vector<int> point; //划分区间的点
    vector<Segment> seg; //线段树存储的数据
    int size;

    //构建树
    void build(int l,int r,int x);

    //这里的pushUp的作用是 如果当前区间被完全覆盖 (sum > 0)，直接计算覆盖长度。
    //如果未完全覆盖，合并子节点的覆盖长度。
    void pushUp(int x);

    //就是统计覆盖次数，递归调用
    void add(int x,long long L,long long R,int num);

    public:
    explicit SegTreeForScanLine(vector<int> p,int size);
    //比较简单代码直接写头文件里面了，只是提供一个调用的接口，不需要求区间加只需要取根节点的len值就行
    long long getRootLen() {
        return seg[1].len;
    }

    void scanLine(long long L,long long R,int num) {
        add(1,L,R,num);
    }
    /*void print() { //测试用
        for(Segment seg : seg) {
            cout << seg.l << " " << seg.r << " " << seg.sum << " " << seg.len << endl;
        }
        putchar('\n');
    }*/
};



#endif //SEGTREEFORSCANLINE_H
